package org.example.code.test2024.eleven;

import org.example.code.test2024.eight_mouth.TreeNode;

import java.util.*;

/**
 * @Title: test1121
 * @Author yxy
 * @Package org.example.code.eleven
 * @Date 2024/11/21 09:42
 * @description:
 */
public class test1121 {

    /**
     * 有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
     * 现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。
     * 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。
     * 求所能获得硬币的最大数量。
     *
     * nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
     * coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167
     * @param nums
     * @return
     */
    public int maxCoins(int[] nums) {
        int[][] dp = new int[nums.length+2][nums.length+2];
        int[] newInt = new int[nums.length+2];
        newInt[0] = 1;
        newInt[nums.length+1]=1;
        System.arraycopy(nums, 0, newInt, 1, nums.length);
        for(int size = 1;size<=nums.length;size++){
            for(int i=1;i<= nums.length-size+1;i++){
                int j = i+size-1;
                for(int k=i;k<=j;k++){
                    dp[i][j] = Math.max(dp[i][j],dp[i][k-1]+dp[k+1][j]+newInt[i-1]*newInt[k]*newInt[j+1]);
                }
            }
        }
        return dp[1][nums.length];
    }

    public TreeNode shiftTree(TreeNode root, int k) {
        if(root == null) return null;
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> list = new ArrayList<TreeNode>();
            for(int i=0;i<size;i++){
                TreeNode node = queue.poll();
                if(node.left != null) queue.add(node.left);
                if(node.right != null) queue.add(node.right);
                list.add(node);
            }
            List<Integer> shifted = new ArrayList<>();
            for(TreeNode value:list){
                shifted.add(value.val);
            }
            int t = k%shifted.size();
            Collections.rotate(shifted, t);
            for(int i=0;i<shifted.size();i++){
                list.get(i).val = shifted.get(i);
            }
        }
        return root;
    }
    public void printTree(TreeNode root) {
        if (root == null) {
            System.out.println("Tree is empty.");
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node != null) {
                    System.out.print(node.val + " ");
                    queue.offer(node.left);
                    queue.offer(node.right);
                } else {
                    System.out.print("null ");
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        BinaryTreeShift solution = new BinaryTreeShift();

        // 构造示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        System.out.println("原始二叉树:");
        solution.printTree(root);

        // 右移每层节点
        int k = 2;
        TreeNode shiftedRoot = solution.shiftTree(root, k);

        System.out.println("右移后的二叉树:");
        solution.printTree(shiftedRoot);
    }


}
